import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
import java.util.Stack;

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if(minStack.isEmpty()) {
            minStack.push(val);
        }else if(minStack.peek() >= val) {
            minStack.push(val);
        }
    }

    public void pop() {
        if(Objects.equals(stack.pop(), minStack.peek())) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

//栈实现队列
class MyQueue {
    Stack<Integer> s1;
    Stack<Integer> s2;

    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }

    public void push(int x) {
        s1.push(x);
    }

    public int pop() {
        if(!s2.isEmpty()) {
            return s2.pop();
        }
        while(!s1.isEmpty()) {
            s2.add(s1.pop());
        }
        return s2.pop();
    }

    public int peek() {
        if(!s2.isEmpty()) {
            return s2.pop();
        }
        while(!s1.isEmpty()) {
            s2.add(s1.pop());
        }
        return s2.peek();
    }

    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

//队列实现栈
class MyStack {
    Queue<Integer> q1;
    Queue<Integer> q2;

    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    public void push(int x) {
        if(!q1.isEmpty()) {
            q1.add(x);
        }else if(!q2.isEmpty()){
            q2.add(x);
        }else {
            q1.add(x);
        }
    }

    public int pop() {
        if(!q1.isEmpty()) {
            int size = q1.size();
            for(int i = 0; i<size-1; i++) {
                q2.add(q1.poll());
            }
            return q1.poll();
        }else {
            int size = q2.size();
            for(int i = 0; i<size-1; i++) {
                q1.add(q2.poll());
            }
            return q2.poll();
        }
    }

    public int top() {
        if(!q1.isEmpty()) {
            int size = q1.size();
            for(int i = 0; i<size-1; i++) {
                q2.add(q1.poll());
            }
            int x =  q1.poll();
            q2.add(x);
            return x;
        }else {
            int size = q2.size();
            for(int i = 0; i<size-1; i++) {
                q1.add(q2.poll());
            }
            int x =  q2.poll();
            q1.add(x);
            return x;
        }
    }

    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }
}


public class Test {
}
